package cn.cxq.learning.string_matching;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 字符串的排列
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：783208
 * 本题知识点： 字符串 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * 输入描述:
 * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 * 示例1
 * 输入
 * 复制
 * "ab"
 * 返回值
 * 复制
 * ["ab","ba"]
 */
public class Permutation {

    @Test
    public void test(){
        ArrayList<String> ab = Permutation("aabc");

        for (String s : ab) {
            System.out.println(s);
        }
    }

    // 动态规划解决问题
    public ArrayList<String> Permutation(String str) {

        if (str.length() == 0) {
            return new ArrayList<>();
        }

        ArrayList<String>[] dp = new ArrayList[str.length()];

        dp[0] = new ArrayList<>();

        dp[0].add(String.valueOf(str.charAt(0)));

        for (int i = 1; i < str.length(); i++) {

            dp[i] = new ArrayList<>();

            for (String s : dp[i - 1]) {
                for (int j = s.length(); j >= 0; j--) {
                    String temp = new StringBuffer().append(s, 0, j)
                            .append(str.charAt(i))
                            .append(s.substring(j))
                            .toString();
                    if (!dp[i].contains(temp)) {
                        dp[i].add(temp);
                    }
                }
            }
        }

        dp[str.length()-1].sort((str1,str2)->{
            for (int i = 0; i < str1.length(); i++) {
                int result = str1.charAt(i) - str2.charAt(i);
                if (result!=0) {
                    return result;
                }
            }
            return 0;
        });

        return dp[str.length() - 1];
    }
}
